package com.kiven.quicksort;

import java.util.Comparator;
/**
 * 这个程序实现的是对一个键值对，根据键值的大小进行排序快速排序
 * 
 * 解决无法用Map来存储的缺陷，这里利用两个数组进行实现，一个数组存放键值，另个数组来存放值，
 * 然后在排序的时候，只需要用到一组下标，这样一组下标的改变对应两个数组的该边就可以实现所要的功能了
 * 
 * @author liqingwen
 *
 */

public class QuickSortForGeneral {
	private MyComparator mc = new MyComparator();
	/**
	 * 实现冒泡排序算法
	 * 冒泡排序算法是快速排序的前身，快速排序是冒泡排序的优化
	 * 
	 * @param keyset 存放键值的数组
	 * @param values 存放键值所对应数值的数组
	 * 
	 * 对于键值数组和数值数组的长度是相同的，因为，它们模拟一一对应的关系。所以它们用的下标表示可以共享
	 * @param left 数组的左小表(下标的最小值)
	 * @param right 数组的右下标(下标的最大值)
	 */
	public void bubbleSort(Object[] keyset,Object[] values,int left,int right) {
		Object temp1,temp2;
		//i：记录比较的次数
		for(int i=0; i<keyset.length; i++) {
			//j：控制比较数组的下标值
			for(int j=i+1; j<keyset.length; j++) {
				//这里就用用到重写的comparable了
				if(mc.compare(keyset[i],keyset[j])>0) {
					//交换键值
					temp1 = keyset[i];
					keyset[i] = keyset[j];
					keyset[j] = temp1;
					
					//交换键值所对应的数值
					temp2 = values[i];
					values[i] = values[j];
					values[j] = temp2;
				}
			}
		}
	}
	
	/**
	 * 快速排序算法(递归)
	 * 
	 * 这个快速排序主要是模拟键值对的数据，根据键值进行排序，跟据所需的要求实现快速排序(这里的不同实现主要是根据重写Comparator接口
	 * 来实现的，在这里写了一个内部比较类MyComparator)，但是有点必须得注意的是，所比较的是键值对，所以，在传入比较的键值时，必须事先
	 * 一一对应(这个是问题的关键)
	 * 
	 * @param keyset 存放键值的数组
	 * @param values 存放键值所对应数值的数组
	 * 
	 * 对于键值数组和数值数组的长度是相同的，因为，它们模拟一一对应的关系。所以它们用的下标表示可以共享
	 * @param left 数组的左小表(下标的最小值)
	 * @param right 数组的长度
	 * 
	 */
	/*public void quickSort(Object[] keyset,Object[] values,int left,int right) {
		Object pivotValue,pivotV,temp1,temp2;  //temp1临时存储键值的中间变量，temp2临时存储数值的中间变量
		int i = left;
		int j = right;
		pivotValue = keyset[left];   //轴点的值
		
		
		
		MyComparator mc = new MyComparator(); //定义一个比较器
		while(true) {
			while((++i) < right-1 && mc.compare(keyset[i], pivotValue)<0);   //从左边开始查找，找出数组中大于pivotValue的位置 
			while((--j)>left && mc.compare(keyset[j], pivotValue)>0);  //从右边开始查找，找出数组中小于pivotValue的位置
			if(i>=j) break;
			else {
				//交换键值
				temp1 = keyset[i];
				keyset[i] = keyset[j];
				keyset[j] = temp1;
				
				//交换键值所对应的数值
				temp2 = values[i];
				values[i] = values[j];
				values[j] = temp2;
			}
		}
		
		//交换移动一轮后左键值和轴点键值的位置
		temp2 = key
		keyset[left] = keyset[j];
		keyset[j] = pivotValue;
		      
        temp1 = keyset[i];
		keyset[i] = keyset[right];
		keyset[right] = temp1;
		
		
		//交换移动后的键值所对应的数值
		temp2 = values[left];
		values[left] = values[j];
		values[j] = temp2;
		
		
		temp2 = values[i];
		values[i] = values[right];
		values[right] = temp2;
		
		if(left < j) {
			quickSort(keyset, values, left, j);
		}
		
		if(right > i) {
			quickSort(keyset, values, i, right);
		}
		
	}*/
	
	public void quickSort(Object[] keyset,Object[] values,int left,int right) {
		Object pivotKey,pivotValue;
		int i = left;
		int j = right;
		pivotKey = keyset[left];
		pivotValue = values[left];
		
		while(i<j) {
			while(i<j && mc.compare(keyset[j], pivotKey)>0) {
				j--;
			}
			if(i<j) {
				keyset[i] = keyset[j];
				values[i] = values[j];
				i++;
			}
			while(i<j && mc.compare(keyset[i], pivotKey)<0) {
				i++;
			}
			if(i<j) {
				keyset[i] = keyset[j];
				values[i] = values[j];
				j--;
			}
		}
		
		keyset[i] = pivotKey;
		values[i] = pivotValue;
		
		quickSort(keyset,values,left,i-1);
		quickSort(keyset,values,i+1,right);
	}
	
	//快速排序(非递归的实现方式)
	public void quickSortNoRecursion(Object[] keyset,Object[] values,int left,int right) {
		LinkedStack ls = new LinkedStack();
		int i = left;
		int j = right;
		int p = -1;
		
		while(true) {
			//得到一轮比较后轴点的最终位置
			p = position(keyset, values, i, j);
			
			/*
			 * 判断该最终位置和最左位置的距离，如果轴点位置的左边右至少还有两个数，那么左边的数要接着进行比较
			 * 于是现在左边的数的左右下标先存在堆栈里，等右边排序完了再接着进行对堆栈中的数弹出进行比较
			 */
			if(p-i>1) {
				ls.push(i, p-1);
			}
			
			//数组轴点左边的数组左右下标压入栈后，对轴点右边的子数组比较
			i = p + 1;
			
			/*
			 * 对下标进行比较，如果左下标已经大于右下标，证明此时已经完成了该子数组的排序了
			 * 此时，判断堆栈中是否存在节点，如果存在的话就将该节点弹出栈，这个节点存的就是字数组的左右下标值
			 */
			if(i>=j) {
				if(!ls.isEmpty()) {
					Node node = ls.pop();
					i = node.getLeft();
					j = node.getRight();
				}
				else break;
			}
		}
		
	}
	
	//快速排序(非递归的实现方式)所需要的得到交换后轴点的位置
	public int position(Object[] keyset,Object[] values,int left,int right) {
		Object pivotValue,temp1,temp2;
		int i = left-1;
		int j = right;
		pivotValue = keyset[right];
		
		while(true) {
			while(mc.compare(keyset[++i], pivotValue)<0);   //从左边开始查找，找出数组中大于pivotValue的位置 
			System.out.println("一轮比较后i的位置：" + i);
			while(j>i && mc.compare(keyset[--j], pivotValue)>0);  //从右边开始查找，找出数组中小于pivotValue的位置
			System.out.println("一轮比较后j的位置：" + j);
			
			/*
			 * 排序前
               键：1   值：LI
               键：1   值：one
               键：1   值：300
               键：1   值：1
               键：1   值：HHH
			 * 
			 * 
			 * 结果
			 * 键：1   值：300
			   键：1   值：1
			   键：1   值：HHH
			   键：1   值：one
			   键：1   值：LI
			 */
			
			if(i>=j) break;
			else {
				//交换键值
				temp1 = keyset[i];
				keyset[i] = keyset[j];
				keyset[j] = temp1;
				
				//交换键值所对应的数值
				temp2 = values[i];
				values[i] = values[j];
				values[j] = temp2;
			}
		}
		
		//交换移动一轮后左键值和轴点键值的位置
		temp1 = keyset[i];
		keyset[i] = keyset[right];
		keyset[right] = temp1;
		
		//交换移动后的键值所对应的数值
		temp2 = values[i];
		values[i] = values[right];
		values[right] = temp2;
		
		return i;
	}
	
	public static void main(String[] args) {
		//注意这里两个数组的长度相同，也就是模拟Map的一一对应的键值对，所以在排序时这里一定要进行控制
		Object[] keyset,values;
		//keyset = new Object[]{"kiven",1,3,"A",2.3};
		keyset = new Object[]{1,1,1,1,1};
		values = new Object[]{"LI","one",300,1,"HHH"};
		
		System.out.println("排序前");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
		
		QuickSortForGeneral qs = new QuickSortForGeneral();
		
		//调用快速排序递归
		qs.quickSort(keyset,values,0,keyset.length-1);
		
		System.out.println("快速排序实现-----排序后");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
		/*
		//调用冒泡排序
		qs.bubbleSort(keyset,values,0,keyset.length-1);
		System.out.println("冒泡排序实现-----排序后");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
		
		
		//调用快速排序(非递归实现方式)
		qs.quickSortNoRecursion(keyset,values,0,keyset.length-1);
		
		
		System.out.println("快速排序非递归方式实现-----排序后");
		for(int i=0; i<keyset.length; i++) {
			System.out.println("键：" +keyset[i] +"   值：" +values[i]);
		}
		 */
		
		
	}
}

/**
 * 这是实现自己要求的比较器类，它实现了Comparator接口，可以根据自己的要求重写其中的Compare方法
 * 对于这个类的内部，也可以跟据不同的要求重载该compare方法，最终实现自己所要求的排序
 * @author liqingwen
 *
 */
class MyComparator implements Comparator {
	/*
	 * 这里的实现的是比较两个数值中间的哈希码大小来判断它们之间的大小
	 * 比较两个数的大小只要返回三种状态(1,0,-1)即可,这样就可以表示大于、等于、小于三种状态
	 * 
	 */
	@Override
	public int compare(Object arg0, Object arg1) {
		int hashcode1 = arg0.hashCode();
		int hashcode2 = arg1.hashCode();
		if(hashcode1 > hashcode2) return 1;
		if(hashcode1 == hashcode2) return 0;
		return -1;
	}
}
